package generateTrees

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/*
给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
*/
/**
二叉搜索树,左子树一定全部小于根节点，右子树一定全部大于根节点
*/
func generateTrees(n int) []*TreeNode {
	var buildTree func(start, end int) []*TreeNode
	buildTree = func(start, end int) []*TreeNode {
		if start > end {
			return []*TreeNode{nil}
		}
		// 存储当前根节点所有可能的树
		tree := []*TreeNode{}

		for i := start; i <= end; i++ {
			//【start, i -1】所有可能的树
			LeftTree := buildTree(start, i-1)
			// 【i + 1, end】 所有可能的树
			RightTree := buildTree(i+1, end)

			// 组合成所有可能的树
			for _, Left := range LeftTree {
				for _, Right := range RightTree {
					// 当前树结点
					cur := &TreeNode{Val: i}
					cur.Left = Left
					cur.Right = Right
					tree = append(tree, cur)
				}
			}
		}
		return tree
	}
	ans := buildTree(1, n)
	return ans
}
